A number of applications, such mapping and navigation applications, rely upon the construction of a traffic prediction model. Although traffic prediction models may be constructed in various manners, some traffic prediction models rely upon a combination of a historic traffic profile and current or real time probe data, such as gathered from various probe sources currently transiting over the roadways. In order to combine the historic traffic profile and the real time probe data, the traffic prediction model determines a weighted average of the real time probe data and historic traffic information derived from the historic traffic profile. The manner in which the real time probe data and the historic traffic information are weighted depends upon the number of available real time probe data points. As more real time probe data points are available, the weighting of the real time probe data increases and the weighting of the historic traffic information correspondingly decreases, thereby creating a bias toward the real time probe data. Conversely, when fewer real time probe data points are available, the weighting of the real time probe data decreases and the weighting of the historic traffic information correspondingly increases, thereby creating a bias toward the historic traffic information.
In certain situations, this technique for constructing a traffic prediction model and, in particular, the manner in which the real time probe data and the historic traffic information are weighted may create unintended and inaccurate results. For example, in an instance in which the traffic flow along a link is slow, fewer vehicles will pass along the link in any particular period of time, thereby resulting in the collection of fewer probe data points along the link. As such, the traffic prediction model may be constructed by more heavily weighting the historic traffic information and more lightly weighting the real time probe data as a result in the reduction in the quantity of real time probe data for the respective link. In an extreme situation, the traffic may be completely blocked along the link so that no real time probe data is received relative to the respective link. In this extreme situation, the historic traffic information may be even more greatly weighted and the real time probe data may be even more lightly weighted. In this regard, the absence of real time probe data along the link may cause the traffic prediction model to be entirely based upon historic traffic information with no reliance upon real time probe data.
As the traffic prediction model places greater weight upon the historic traffic information in instances in which the traffic flow along a respective link is much slower than normal or completely blocked, the greater reliance upon historic traffic information may generate inaccurate results since the historic traffic information generally represents the average flow of traffic along the respective link and not the much slower flow of traffic that is experienced when the link is partially or fully blocked or when the traffic is sluggish for whatever reason. Thus, the resulting traffic prediction model may paint an inaccurate picture as to the traffic conditions along the respective link by predicting that the traffic is progressing at an average flow rate based upon the historic traffic information as opposed to predicting the sluggish or blocked traffic conditions actually experienced by the link.
In conjunction with navigation and other mapping applications, a router employs a greedy minimization strategy with reliance upon the traffic prediction model to generate a route that minimizes the cost between two points, such as an origin and a destination. The cost to be minimized by the router may be the estimated travel time along a route which, in turn, is generally inversely proportional to the speed of travel along the links that comprise the route. The cost function to be minimized by the router may be a random distribution around the real cost, that is, the estimated travel time along the route having natural noise. In this regard, the fewer real time probe data points that are utilized to estimate the cost of a respective link, the greater the local noise and thus the higher the optimistic bias for routing. As a result of its implementation of the greedy minimization strategy, the router is configured to be biased toward links which are currently underestimating the real cost in the course of minimizing the cost between two points. Thus, in instances in which traffic along a link is slowed or blocked and the traffic prediction model relies more greatly upon historic traffic information which overestimates the speed of travel along the respective link, the router may frequently select the links that are, in fact, slowed or blocked as a result of the overestimated speed of travel along the link. Thus, a driver may be directed along a route that includes links that are slowed or blocked which may understandably decrease the user experience as well as the confidence that the driver has in the navigation system. Correspondingly, the estimated time of arrival at the destination that is calculated by the navigation system may prove to be inaccurate as a result of the reliance upon the traffic prediction model that, in turn, more greatly relies upon historic traffic information which may not be appropriate for links that are slowed or blocked.
By way of example, a grid of roadways may exist in which the real speed of traffic along each of the roadways is 30 miles per hour (mph). The natural local noise of the real speed along each of the roadways of this example is 50%. In an instance in which there are very few real time probe data points, the traffic prediction model may more greatly weight historical traffic data such that the speed of every link is within a range of 15 mph to 45 mph, e.g., 30 mph +/− 50%. As such, for a fixed route that includes more than two links, the local random noise will be smoothed or cancelled. However, a router configured to minimize the time of travel along a route will be biased toward the selection of links having a speed of travel of 45 mph. As such, the resulting route may take odd and indirect detours in an effort to remain upon links that appear to have a current speed of 45 mph and to avoid links that appear to have a current speed of 30 mph or even 15 mph. As each link actually has approximately the same real speed of travel, the resulting route generated by the router may, in fact, take longer to traverse than a more direct route between the origin and the destination. Thus, the route generated by the router based upon the traffic prediction model may be suboptimal and the estimated time of arrival based upon a route including links apparently supporting traffic at a speed of 45 mph when, in reality, the traffic is moving along the links at 30 mph may also be overly optimistic.
As another example, a section of a highway may be experiencing a traffic jam. As such, multiple probe data points are available from vehicles mired within the traffic jam such that the traffic prediction model may accurately predict the speed along that segment of the highway. However, a small number of vehicles may transit along a ramp connected to the segment of the highway that is experiencing the traffic jam such that there are a small number of real time probe data points associated with the ramp. The traffic prediction model may therefore determine that the traffic flow along the ramp is proceeding at a much greater speed than the traffic flow along the section of the highway that is experiencing the traffic jam and a router relying upon the traffic prediction model may suggest routes for drivers that includes travel along the ramp. However, if the ramp were, in fact, a better and faster alternative to the section of the highway experiencing the traffic jam, many drivers would actually be using the ramp to take advantage of the increased rate of travel along the ramp so as to avoid, at least in part, the traffic jam experienced by the section of the highway. In this example, however, the Nash equilibrium postulate suggests that the few number of real time probe data points associated with the ramp actually indicates that the ramp is not a viable alternative to the section of the highway experiencing the traffic jam such that the route generated by the router based upon the traffic prediction model that recommends travel along the ramp will be suboptimal.